package com.zx._12_算法.数据结构.stack;

public class Demo3 {

    //实现一个栈，除了常见的push，pop方法以外，提供一个min方法，返回栈里最小的元素，且时间复杂度为o(1)
	/*
		思路分析
		使用两个栈来存储数据，其中一个命名为data_stack,专门用来存储数据，另一个命名为min_stack，
		专门用来存储栈里最小的数据。
	
		注意了，我接下来的分析过程非常重要，我希望你能多阅读几遍。
	
		我们要实现的是一个栈，除了常规的方法，还要有一个min方法，data_stack就是专门为常规方法而存在的，
		min_stack就是为了这个min方法而存在的。
	
		编程思想里有一个分而治之的思想，简单来说，就是分开想，分开处理。那么我们现在考虑data_stack，
		这个时候别管min方法，你就只关心data_stack，它就是一个普通的栈啊，没什么特别的，
		一个简单的栈你还不会么，就是push，pop那些方法，正常实现就可以了。
	
		data_stack处理完了以后，再考虑min_stack，这个时候，你就别想data_stack了，
		只关心min_stack，它要存储栈里的最小值，我们先考虑边界情况，如果min_stack为空，
		这个时候，如果push进来一个数据，那这个数据一定是最小的，所以此时，直接放入min_stack即可。
		如果min_stack不为空，这个时候它的栈顶不正是栈的最小元素么，如果push进来的元素比栈顶元素还小，
		放入min_stack就好了，这样，min_stack的栈顶始终都是栈里的最小值。
	 */
    public static void main(String[] args) {
        Stack3 stack = new Stack3();

        stack.push(3);
        stack.push(6);
        stack.push(8);
        System.out.println(stack.min());
        stack.push(2);
        System.out.println(stack.min());

        System.out.println(stack);

    }

}
